package cn.suchan.jianzhi.sort;

/**
 * 希尔排序
 *
 * @author suchan
 * @date 2019/06/18
 */
public class ShellSort {
    public void sort(int[] array) {
        if (array.length <= 1) {
            return;
        }
        int gap = array.length / 2;
        while (gap > 0) {
            for (int i = gap; i < array.length; i++) {
                int temp = array[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && array[preIndex] > temp) {
                    array[preIndex + gap] = array[preIndex];
                    preIndex -= gap;
                }
                array[preIndex + gap] = temp;
            }
            gap /= 2;
        }
    }

    public static void main(String[] args) {
        ShellSort sort = new ShellSort();
        int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        sort.sort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.printf(array[i] + " ");
        }
    }
}
